package com.wzq.solution;

import com.wzq.solution.node.ListNode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution23 {

    public static ListNode mergeKLists(ListNode[] lists) {

        ListNode head = null;
        ListNode tail = null;
        ListNode p = null;
        while (true){
             p = null;
             int im = 0;
            for(int i=0;i<lists.length;i++){
                if(lists[i] != null){
                    if(p == null){
                        p = lists[i];
                        im=i;
                    }else{
                        if(p.val>lists[i].val){
                            p = lists[i];
                            im=i;
                        }
                    }
                }
            }
            if(p == null){
                break;
            }
            lists[im] = lists[im].next;
            if(head == null){
                head = p;
            }else{
                tail.next = p;
            }
            tail = p;
    
        };
        
        return head;
    }


    public static ListNode mergeKLists2(ListNode[] lists) {
        int len = lists.length;
        if(len == 0){
            return null;
        }
        ListNode head = new ListNode(0);
        head.next = lists[0];
        for(int i=1;i<len;i++){
            ListNode p = head;
            ListNode n = lists[i];
            while(n != null){
                while(p.next != null && p.next.val <= n.val){
                    p = p.next;
                }
                if(p.next == null){
                    p.next = n;
                    break;
                }else{

                    ListNode tp = p.next;
                    ListNode tn = n;
                    n = n.next;

                    p.next = tn;
                    tn.next = tp;

                }
            }
        }

        return head.next;
    }

    public static ListNode mergeKLists3(ListNode[] lists) {
        int len = lists.length;
        if(len == 0){
            return null;
        }
        ListNode head = lists[0];
        for(int i=1;i<len;i++){
            head = mergeList(head,lists[i]);

        }

        return head;
    }


    public static ListNode mergeList(ListNode l1,ListNode l2) {
        ListNode newL = null;
        ListNode tail = null;
        ListNode p;
        while (l1!=null && l2!=null){
            if(l1.val<l2.val){
                p = l1;
                l1 = l1.next;
            }else{
                p = l2;
                l2 = l2.next;
            }
            if(newL == null){
                newL = p;
            }else{
                tail.next = p;
            }
            tail = p;
        }
        if(l1!=null){
            if(newL == null){
                newL = l1;
            }else{
                tail.next = l1;
            }
        }

        if(l2!=null){
            if(newL == null){
                newL = l2;
            }else{
                tail.next = l2;
            }
        }
        return newL;
    }

    public static void main(String[] args) {
        int[][] intArr = new int[][]{{1,4,5},{2,6},{1,3,4}};
        ListNode[] lists = new ListNode[intArr.length];

        for (int i=0;i<intArr.length;i++){
            ListNode head = new ListNode(intArr[i][0]);
            ListNode p =head;
            for (int j=1;j<intArr[i].length; j++){
                p.next = new ListNode(intArr[i][j]);
                p = p.next;
            }
            lists[i] = head;
        }


        mergeKLists3(lists);

    }
}